package nqueens.algorithm;

import java.util.*;
import nqueens.chessStuff.*;

public class ExhaustiveAlgorithm extends Algorithm {

    @Override
    protected void solve(int n) throws InterruptedException {
        int squaresCount = n*n;
        List <Integer> nList = new ArrayList<Integer>();
        for (int ii = 0; ii < squaresCount; ii++) {
            nList.add(ii);
        }

        CombinationGenerator <Integer> cg = new CombinationGenerator<Integer>(nList, n);

        for (List <Integer> l : cg) {
            setChessBoard(convertToChessBoard(l));
            if (validateSolution()) {
                setLastSolutionSolved(getChessBoard());
                break;
            }
        }
    }

    @Override
    protected boolean validateSolution() {
        return getChessBoard().isSolved();
    }

    /**
     *
     * @param q A list queens with their corresponding index based upon a single linear array representation     *
     * @return The chessboard where the placement is as referenced per the array passed as argument
     * @throws InterruptedException
     */
    public ChessBoard convertToChessBoard (List <Integer> q) throws InterruptedException {
        int N = q.size();
        ChessBoard tempBoard = new ChessBoard(N, isValidatingSolutions());
        for (Integer i : q) {
            int row = i.intValue() / N;
            int col = i.intValue() % N;
            tempBoard.placeQueen(row, col);
        }
        return tempBoard;
    }

    /**
     * This was borrowed verbatim from http://big-o.nl/demos/math/combinationgenerator/index.html
     * This takes two arguments, n and k for a standard n choose k combination problem which esentially
     * solves for the binomial coefficient solution.  We already handed in a solution to this algorithm but
     * it was fairly hacky and as opposed to re-inventing the wheel, we just pulled down this version
     * which is much cleaner than our original attempt.
     * @param <E> The element type contained in the list
     */
    class CombinationGenerator<E> implements Iterator<List<E>>, Iterable<List<E>> {

        private final List<E> set;
        private int[] currentIdxs;
        private final int[] lastIdxs;

        public CombinationGenerator(List<E> set, int r) throws InterruptedException {
            if (r < 1 || r > set.size()) {
                throw new IllegalArgumentException("r < 1 || r > set.size()");
            }
            this.set = new ArrayList<E>(set);
            this.currentIdxs = new int[r];
            this.lastIdxs = new int[r];
            for (int i = 0; i < r; i++) {
                this.currentIdxs[i] = i;
                this.lastIdxs[i] = set.size() - r + i;
            }
        }

        @Override
        public boolean hasNext() {
            return currentIdxs != null;
        }

        @Override
        public Iterator<List<E>> iterator() {
            return this;
        }

        @Override
        public List<E> next() {
            if (!hasNext()) {
                throw new NoSuchElementException();
            }
            List<E> currentCombination = new ArrayList<E>();
            for (int i : currentIdxs) {
                currentCombination.add(set.get(i));
            }
            setNextIndexes();
            return currentCombination;
        }

        @Override
        public void remove() {
            throw new UnsupportedOperationException();
        }

        private void setNextIndexes() {
            for (int i = currentIdxs.length - 1, j = set.size() - 1; i >= 0; i--, j--) {
                if (currentIdxs[i] != j) {
                    currentIdxs[i]++;
                    for (int k = i + 1; k < currentIdxs.length; k++) {
                        currentIdxs[k] = currentIdxs[k - 1] + 1;
                    }
                    return;
                }
            }
            currentIdxs = null;
        }
    }
}
